#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* directions of LCS generation */
enum decrease_dir_t {d_init = 0, d_left, d_up, d_leftup};


/* Print a LCS for two strings
 * Input: lcs_direction - a 2d matrix which records the direction of
 *                         lcs generation
 *	  pstr1         - the first string
 *	  pstr2         - the second string
 *	  row           - the row index in the matrix lcs_direction
 *	  col           - the column index in the matrix lcs_direction
 */
static void lcs_print(int **lcs_direction,
	       char *pstr1, char *pstr2,
	       size_t row, size_t col) {
  size_t len1, len2;
  if (NULL == pstr1 || NULL == pstr2)
    return;

  len1 = strlen(pstr1);
  len2 = strlen(pstr2);

  if (0 == len1 || 0 == len2 || !(row < len1 && col < len2))
    return;

  if (d_leftup == lcs_direction[row][col]) {
    /* d_leftup implies a char in the LCS is found */
    if (row > 0 && col > 0)
      lcs_print(lcs_direction, pstr1, pstr2, row - 1, col - 1);

    /* print the char */
    printf("%c", pstr1[row]);
  } else if (d_left == lcs_direction[row][col]) {
    /* move to the left entry in the direction matrix */
    if (col > 0)
      lcs_print(lcs_direction, pstr1, pstr2, row, col - 1);
  } else if (d_up == lcs_direction[row][col]) {
    /* move to the up entry in the direction matrix */
    if (row > 0)
      lcs_print(lcs_direction, pstr1, pstr2, row - 1, col);
  }
}

/* Get the length of two strings' LCSs, and print one of the LCSs
 * Input: pStr1    - the firest string
 *        pStr2    - the second string
 * Output: the length of two strings' LCSs
 */

int lcs(char *pstr1, char *pstr2) {
  size_t len1, len2;
  size_t i, j;
  int **lcs_length = NULL;
  int **lcs_direction = NULL;
  
  if (NULL == pstr1 || NULL == pstr2)
    return 0;

  len1 = strlen(pstr1);
  len2 = strlen(pstr2);
  if (0 == len1 || 0 == len2)
    return 0;

  /* initiate the length matrix */
  lcs_length = (int **)malloc(sizeof(int *)*len1);
  for (i = 0; i < len1; ++i)
    lcs_length[i] = (int *)malloc(sizeof(int)*len2);

  for (i = 0; i < len1; ++i)
    for (j = 0; j < len2; ++j)
      lcs_length[i][j] = 0;

  /* initiate the direction matrix */
  lcs_direction = (int **)malloc(sizeof(int *)*len1);
  for (i = 0; i < len1; ++i)
    lcs_direction[i] = (int *)malloc(sizeof(int)*len2);

  for (i = 0; i < len1; ++i)
    for (j = 0; j < len2; ++j)
      lcs_direction[i][j] = d_init;

  for (i = 0; i < len1; ++i) {
    for (j = 0; j < len2; ++j) {
      if (0 == i || 0 == j) {
	if (pstr1[i] == pstr2[j]) {
	  lcs_length[i][j] = 1;
	  lcs_direction[i][j] = d_leftup;
	} else {
	  if (i > 0) {
	    lcs_length[i][j] = lcs_length[i - 1][j];
	    lcs_direction[i][j] = d_up;
	  }
	  if (j > 0) {
	    lcs_length[i][j] = lcs_length[i][j - 1];
	    lcs_direction[i][j] = d_left;
	  }
	}
      } else if (pstr1[i] == pstr2[j]) {
	/* a char of LCS is found, it comes from the left up entry in
	   the direction matrix */
	lcs_length[i][j] = lcs_length[i - 1][j - 1] + 1;
	lcs_direction[i][j] = d_leftup;
      } else if(lcs_length[i - 1][j] > lcs_length[i][j - 1]) {
	lcs_length[i][j] = lcs_length[i - 1][j];
	lcs_direction[i][j] = d_up;
      } else {
	lcs_length[i][j] = lcs_length[i][j - 1];
	lcs_direction[i][j] = d_left;
      }
    }
  }
  /* call lcs_print() to print the max substring */
  lcs_print(lcs_direction, pstr1, pstr2, len1 - 1, len2 - 1);

  /* return length */
  return lcs_length[len1 - 1][len2 - 1];
}
